This invention relates generally to data storage and more particularly to a method and system for testing linked list integrity.
Telecommunications is becoming increasingly important in today""s society. The increased use of the Internet allows people to communicate data between home or business and remote locations. One format for communicating data is asynchronous transfer mode (ATM) format. Many other formats also exist.
Among other criteria, when communicating information according to ATM, cells of data of a specified size are transmitted from one location to another. Often times the cells are stored in memory at an intermediate location before being transferred to the desired destination. An example of such a procedure is the use of an ATM switch at a telecommunications central office for switching data originating from a user""s home over the Internet to an appropriate destination over an Internet backbone. Such cells are often scored in a sequential manner such that data that are received first by the memory are distributed first. To effect such sequential transmission, queues are formed that designate which cells are transferred first. In some implementations, a queue exists for each destination. Such procedures apply to some communications formats other than ATM.
Linked lists are used in some systems to store queues of ATM cells (or other types of data) to facilitate sequential transmissions. Linked lists may be formatted in a variety of fashions; however, linked lists generally link together subsequent addresses in linked memory that are associated in some way with addresses in cell memory. The memory location in cell memory associated with the cell memory addresses actually store that data.
A problem with linked lists is that the entire linked list is lost if any of the pointers become corrupted.
According to one embodiment of the invention, a method is provided for testing linked list integrity. The method includes storing a plurality of link pointers in memory in association with respective integrity parameters. The link pointers point to a next location in the memory storing a subsequent link pointer in the linked list. The method also includes reading the stored integrity parameter for at least one of the link pointers. The method also includes determining whether the value of the read integrity parameter matches the value of the stored integrity parameter.
Some embodiments of the invention provide numerous technical advantages. Other embodiments may realize some, none, or all of these advantages. For example, according to one embodiment, the integrity of linked lists may be easily determined, which allows selective use of corrupted memory locations without having to reset the entire card that may be associated with the memory. This allows for more robust operation of whatever device utilizes the linked list, whether the device be an ATM switch or other device. Additionally, according to one embodiment, a count of memory locations that are corrupted may be maintained. Such a count facilitates discarding and replacing a corrupt device at an appropriate time.
Other technical advantages may be readily ascertained to one of skill in the art.